其他
2023年，量子算法的应用清单（下篇）
组合优化问题是指在有限的候选方案中寻求最优解的任务。在工业环境中，组合优化产生于调度、路由、资源分配、供应链管理和其他物流问题，在这些问题中，很难找到符合各种预期约束条件的最优解。
运筹学在二战军队面临的物流问题中得到应用后开始崭露头角，它将组合优化（以及连续优化）方法应用于这些问题领域，以改善现实问题中的决策和效率。
组合优化问题也是经典理论计算机科学的核心问题，它们被用来描述和划分复杂性类别。典型的组合优化问题可利用的结构有限，因此量子计算通常只能提供多项式加速。事实上，在量子计算研究的早期，量子计算机确实通过Grover搜索算法为各种各样的此类问题提供了高达四次方的速度提升，这让人大吃一惊。随后，人们投入大量精力了解Grover搜索及其广义算法振幅放大是如何为各种组合优化问题提速的。
在本节中，我们将介绍解决组合优化问题的几种不同方法。首先，我们通过组合优化与搜索问题的关系来研究组合优化问题，Grover算法或其广义算法可以在这些问题上实现二次或二次以下的提速；然后，我们将介绍几种有可能超越Grover算法二次提速的建议：变量算法（被视为精确算法）、绝热算法和“短路径”算法。我们讨论了这些方法可能产生显著优势的（有限但已有的）证据，以及相关的注意事项。
我们没有专门讨论大量关于近似组合优化的量子方法（通常是变分量子算法或量子退火）。这些算法通常将优化问题转化为自旋系统的能量最小化问题，自旋系统的哈密顿能编码经典目标函数。它们应用一些物理启发式方法，高效生成低能耗的解决方案，并希望在可比时间内获得比经典方法更好的目标值。这些方法的一个优势是，它们通常与NISQ硬件更加兼容。
虽然近似优化仍是一个有趣的方向，但这些量子算法都是启发式的，而且普遍缺乏具体证据证明它们能带来实际优势。
1）Grover搜索算法
Grover搜索算法及其广义算法（如振幅放大），是量子提速的重要来源。Grover搜索在优化方面的一个直接应用是量子最小值搜索，它能以二次加速找到给定元素集合上函数的最小值。
由于搜索是一种非常通用的原始算法，Grover算法的适用范围非常广泛、可以加快许多子程序的速度，尤其是在组合优化算法中。在量子计算的早期，人们发现了大量这样的应用，而且这个列表还在不断扩大。
关于Grover型（次）二次加速的资源估算，已有多项研究。不幸的是，这些最新研究表明，除非容错量子计算方案的巨大开销能够大大降低，否则仅靠二次加速或更小的加速，即使在中期也不太可能有用。例如，有文献指出：“即使只考虑能在一天内解决的问题实例，我们也会发现量子计算速度可能会大幅提升。... 然而，所使用的物理量子比特数量极其庞大，......。特别是，如果算上使用当前技术对表面代码进行解码所需的经典处理能力的成本，量子优势就会消失”。 根据上述最新论文估计，如果每次迭代至少包含一次浮点运算，那么通过二次加速获得量子优势至少需要一个月的计算时间。
三次和四次加速的情况看起来更有希望，但不幸的是，这种改进似乎需要Grover搜索以外的技术。
Grover最初将他的成果描述为“用于数据库搜索的快速量子力学算法”。如果我们在量子计算的电路模型中工作，那么严格来说，Grover搜索会降低数据库搜索的速度，因为Grover的每次迭代都需要“接触”数据库中的每个元素。如果我们无论如何都需要“接触”数据库中的所有N个元素，那么我们能做的最好的方法就是在线性时间筑(N)内简单地遍历每个元素。
在这种情况下，Grover的搜索电路的门复杂度为
在数据库场景中，只有假设我们可以使用量子随机存取存储器(QRAM)，每次数据库查询的成本不变（或对数），我们才能恢复四倍速度。经典计算机科学中通常会对普通RAM做出类似假设，原因很简单，因为RAM调用在实践中很便宜。然而，由于RAM调用应能触及数据库的每个位，因此从电路复杂度的角度来看，RAM调用的门成本必须至少为N。另一方面，这项任务可以很好地并行化，因此在适当的硬件条件下，RAM调用的（时间）复杂度为log(N)是合理的。特别地，如果需要纠错，特别是以容错方式实现整个QRAM电路时，类似的计算对QRAM来说可能并不公平。
不过，当我们搜索的列表元素可以很容易地“即时”生成和检查时，Grover算法无需额外的硬件假设，就能实现四倍的速度提升。例如，在SAT的情况下，我们要搜索2^n个可能的真值赋值，但我们只需将赋值代入公式并评估所得到的布尔表达式，就能轻松检查单个赋值是否令人满意。
我们讨论了格罗弗搜索如何为SAT带来二次加速，以及振幅放大如何为3-SAT带来二次加速。Grover算法还可用作其他一些组合优化问题的辅助线，例如与图有关的问题。如上所述，容错资源估算无论如何都是不利的。
与量子计算有关的一个经常被提及的图问题是（著名的）旅行推销员问题。然而，对于这个问题，可证明的最佳提速只是亚二次方。经典问题运行时间为n！，而Grover算法比它快了四倍。不幸的是，最佳经典算法使用动态编程，运行时间为2^n。
考虑到实施QRAM和容错带来的开销，旅行推销员问题似乎是最不可能实现实际量子提速的问题之一。
最后，让我们提一下量子随机游走算法，它也可以被看作是Grover搜索的一般化。不过，量子随机游走是Grover搜索的“远亲”，只能应用于更特殊的环境中。量子随机游走可用于证明查询复杂度的许多非小加速，但由于空间和/或门复杂度开销较大，所产生的算法往往并不实用。
不过，还有更实用的量子行走算法，例如，可用于加速反向追踪算法，这是在实际求解SAT实例时最成功、最广泛使用的经典启发式算法之一。与经典的反向追踪算法相比，量子算法基本上可以实现二次加速：这种方法适用于图的阶数最多为4的特殊情况下的旅行推销员问题。
该算法的进一步扩展适用于分支限界法，在某些情况下，其运行时间大大优于我们所知道的通过使用Grover算法所能达到的结果。基于分支限界法的提速还可用于求解混合整数程序，其中包括投资组合优化问题的某些公式。
量子搜索提速的其他应用还有很多，从机械学习到其他NP难问题的动态编程求解。
2）在精确组合优化中超越二次加速
Grover算法（后来被推广到振幅放大）的发现长期以来一直是量子算法在组合优化方面具有优势的热情源泉，因为它为该领域的许多具体端到端搜索问题带来了四次渐近加速。然而，资源估算表明，与经典计算相比，由于量子计算的内在开销，当可用速度提升仅为二次方时，早期和中期容错设备将无法带来实际优势。
因此，确定是否存在超越二次的加速对于确定组合优化中端到端的实际优势至关重要。尽管Grover算法在黑箱（非结构化）环境中是最优的，但如果组合优化问题具有某种结构，量子算法比经典算法能更好地利用这种结构，那么就有可能实现超四次方加速。
遗憾的是，许多可以实现超二次加速的方案都缺乏严格的理论性能保证：这包括量子绝热算法和变分量子算法，如量子近似优化算法(QAOA)，该算法通常用于给出近似解，但成本较高时也可用于找到精确解。现在，已经有有限的分析和数值工作提供了一些证据，证明QAOA在k-SAT问题上的表现可能优于Grover算法的虚构应用，但并未就此得出明确结论。另外，还有文献研究了一种不同的算法（在某些方面与量子绝热算法相关），并提供了严格的运行时间保证，略微超过了Grover算法。
不过，虽然这些算法可能比Grover算法更快，但这并不意味着比最佳经典算法有超四倍的速度提升，因为最佳经典算法往往可以通过其他方式利用结构，比穷举搜索做得更好。总之，量子算法能否为精确组合优化中的有用问题提供超四次方速度，这仍然是一个悬而未决的问题。
有几个注意事项。其中最突出的一点是，对于大多数算法而言，都不存在可证明的超越Grover的优势。同时，就算法而言，可证明的超越Grover优势的大小微乎其微。因此，这些算法的前景只能依靠在极小实例规模下进行的数值模拟和基于物理原理的推测。
第二个重要注意事项是，要实现实际的超四次方加速，量子算法的性能需要与最佳经典算法进行比较，而最佳经典算法的性能往往大大优于穷举法的O* (2^n) 运行时间。
沿着这些思路，第三个注意事项是经典“量子蒙特卡罗”算法的存在，在某些条件下，它们可以经典地模拟上述量子算法。随机性意味着哈密顿的基态可以写成所有振幅都是非负实数，这意味着这些哈密顿避免了所谓的“符号问题”，使量子蒙特卡罗技术的潜在应用成为可能。需要明确的是，对于这些涉及随机哈密顿的组合优化问题，量子算法仍有可能避开经典模拟：事实上，经典计算与仅限于随机路径的绝热量子计算之间的超多项式oracle分离已经被证明，但这是在设计基于随机哈密顿的算法时需要牢记的一点。
最后需要注意的是，这里描述的量子算法通常不适合并行化，尽管如果选择不使用幅值放大（导致渐进复杂性更差），QAOA原则上是可以并行化的。这与许多用于精确组合优化的经典优化算法形成了鲜明对比：后者具有很强的可并行性，利用这一特点可以显著缩短这些分类算法在高性能计算机上的运行时间，从而使实现实用量子优势变得更加困难。
由于量子算法通常没有严格的运行时间保证，因此无法估算速度提升。不过，值得强调的是，对于困难的组合优化问题，加速可能是超二次方的，但预计不会是四次多项式的。
QAOA方法也适合于NISQ实现（假设不在其上应用振幅放大），因为需要实现的量子电路深度较浅。在这种情况下，NISQ设备中未修正的误差可能会降低性能（需要更多的重复才能提取出最佳比特串z*）。同样，在NISQ量子退火器上，可以运行量子绝热算法的噪声版本，并重复直到找到最佳比特串 z* 。
量子计算机要想对精确组合优化产生影响，必须做到以下两点之一：1）量子硬件的预期底层时钟速度和容错量子计算的开销取得巨大进步；或2）量子算法的开发大大超过Grover算法提供的四倍速度。
一方面，已经有人提出了有可能实现这种加速的想法，但另一方面，在所有情况下都没有可证明的保证，或者可证明的保证非常小。如果我们想利用量子算法带来实际优势，就必须投入更多精力研究这些量子算法并开发新算法，尤其是考虑到针对这些问题开发复杂经典算法的大量工作。
连续优化问题出现在科学和工业领域。从表面上看，连续优化问题似乎很少涉及量子力学；然而，人们已经提出了量子算法来加速凸和非凸连续优化。迄今为止，关于这些算法的大部分研究都是为了开发和利用在这一领域产生潜在量子优势的各种原始成分，而没有着眼于算法的端到端实用性。
更好地理解这些方法的实用性应该是未来工作的重点。
1）零和博弈：计算纳什均衡
在双人零和博弈中，每个博弈者都会独立选择一种策略，然后获得“报酬”（报酬之和总是为零），而“报酬”取决于选择了哪一对策略。
纳什均衡是概率选择策略的最优方式，它能使玩家的最坏情况报酬最大化。计算纳什均衡的问题在某种意义上等同于求解线性规划(LP)：计算纳什均衡是LP的一个特例，反过来说，任何LP都可以简化为计算纳什均衡，但代价是要引入某个特定实例的“规模不变”精度参数。然而，在计算纳什均衡的特殊情况下，基于乘法权重更新方法(multiplicative weights updatemethod)的量子LP求解方法更为高效，而且注意事项更少。
与经典方法相比，它的速度可能会提高四倍。
双人零和博弈是由一个n题m矩阵A（称为“报酬矩阵”）定义的，它规定了当玩家1使用（纯）策略和玩家2使用（纯）策略时，玩家1从玩家2那里赢了多少。纯策略是指玩家在每局游戏中使用一种固定策略。相比之下，混合策略是指棋手根据某种概率分布随机选择一种纯策略。纳什均衡是一种最优策略（通常是混合策略），它能使棋手的最坏情况收益最大化，而与其他棋手的选择无关。
该算法没有现有的误差修正资源估算值。量子复杂性的复杂度与参数n+m相比有四次方的提高，与参数ϵ相比有多项式的减慢。
如果不进一步研究如何完成对矩阵元素的查询，不评估算法中涉及的常量因素，不考虑容错量子计算带来的额外开销，就很难评估在零和博弈中是否能获得实际优势。理论上的速度提升是四次方的，可能需要中型或大型QRAM；在实际应用中，这种提速可能不足以克服这些开销。
将零和博弈的前景与一般的圆锥曲线编程进行比较或许会有所启发。一方面，与一般SDP和LP算法不同，零和博弈算法的复杂度并不依赖于表示主解和对偶解大小的特定实例参数。这使得算法的运行时间更容易评估，也更有可能成为一种有效的算法。另一方面，量子算法的核心子程序是利用振幅放大等技术，以比经典计算机快四倍的速度进行经典吉布斯采样。然而，即使在特殊情况下，也不清楚如何才能使速度提高到四倍以上。解决SDP的乘法权重方法也需要类似的子程序，但在这种情况下，需要采样的吉布斯状态是真正的量子态（即计算基础中的非对角线），而不是经典态。利用更先进的吉布斯采样方法，在某些特殊情况下，有可能实现SDP的超四次量子加速——而这是LP和零和博弈等更简单的情况所不具备的。
2）圆锥曲线编程：求解LP、SOCP和SDP
圆锥曲线程序是凸优化问题的一个特定子类，其中目标函数是线性的，凸约束是对仿射空间与Rn中某些圆锥的交点的限制。常见的圆锥有正交圆锥、二阶圆锥（“冰淇淋圆锥”）和半定锥，它们分别产生了线性程序(LP)、二阶圆锥程序(SOCP)和半定锥程序(SDP)。
这一框架仍具有相当的通用性，现实世界中的许多问题都可以简化为圆锥程序。然而，与完全一般的凸问题相比，程序的附加结构允许采用更高效的经典算法和量子算法。
LP、SOCP和SDP算法一直是研究的主题。目前，最好的经典算法是基于内点法(IPM)，但也有其他基于乘法权值更新法(MWU)的算法，在不需要高精度的情况下，这些算法可能更胜一筹。这两种方法都可以转化为量子算法，有可能为一般LP、SOCP和SDP提供渐近量子加速。不过，量子算法的运行时间通常取决于额外的特定实例参数，因此很难与经典算法进行一般的对比。
对于IPM和MWU方法来说，量子提速最多只能达到多项式：在经典和量子情况下，随n多项式缩放的上下限都是已知的。QIPM方法的提速取决于κ随n的缩放，但提速不会超过二次方。假定稀疏性不变，MWU方法在n缩放方面的提速可以达到二次方。如果吉布斯采样例程在实践中比其最坏情况上限所显示的速度更快，那么在利用蒙特卡罗式方法进行吉布斯采样时，速度提升有可能会更大。
使用MWU方法求解LP或SDP，在问题规模上获得渐近多项式加速是非常有可能的，但这种加速似乎只是二次方加速，而实用性的评估取决于某些未指定的特定实例参数的比例。同样，QIPM方法也能带来亚二次方的加速，但前提是对某些矩阵的条件数有一定的假设。 在考虑了纠错开销和较慢的量子时钟速度后，仅凭这些二次方和亚二次方加速可能不太可能带来实际的加速。
未来的工作应着眼于找到更多的渐进提速，同时关注允许对未指定参数进行评估的特定实际相关用例。
3）一般凸优化
凸问题要求在凸集合K上优化一个凸函数f，其中K是Rn的一个子集。在这里，我们研究的是f(x)的值和x在集合K中的成员资格都可以通过经典方法有效计算的情况。这种情况与求解圆锥曲线程序的情况截然不同，在后者中，f是线性的，而K是凸锥和仿射空间的交集，利用这些特征可以产生更高效的经典算法和量子算法。
目前还没有针对这种算法的资源估算。如果没有更具体的方案，进行这样的估算可能没有意义，因为估算结果将在很大程度上取决于执行电路的复杂性。
对这一策略的唯一分析是理论性的，更关注的是解决这一问题的查询复杂性，而不是它可能具有的任何具体应用。因此，分析不够精细，无法确定常数因子或对数微分因子的影响。虽然查询复杂度可能会有四次方加速，但门复杂度的最大加速却小于四次方。此外，还缺乏符合“无结构”量子凸优化范例的具体问题。
这些因素加在一起，使得在这种情况下不太可能找到实用的量子优势。
4）非凸优化：摆脱鞍点并找到局部最小值
寻找非凸优化问题的全局最小值具有挑战性，因为局部算法会陷入局部最小值。
通常情况下，会有很多局部极小值，而且每个极小值之间都有很大的能量障碍。因此，人们可能会选择寻找局部最小值，而不是寻找全局最小值：在训练机器学习模型等情况下，局部最小值通常仍可有效利用。寻找局部最小值的有效方法是梯度下降法，但梯度下降法可能会遇到卡在鞍点附近的问题。因此，要有效地找到局部最小值，就必须找到摆脱鞍点的方法。
该领域有限的研究表明，利用哈密顿模拟和量子梯度估计子程序，在寻找局部极小值的维度依赖性方面，可能会有多项式量子加速。
目前，对这一问题的关注相对较少，也没有进行过资源估算。
现在也还不清楚寻找局部极小值的算法是否能带来实际的加速，因为它在很大程度上取决于是否有高效的经典程序来实现梯度查询；只有当这种查询难以经典地实现时，量子加速才有可能。不过，该算法代表了一个有用的端到端问题，可以应用量子梯度估计原语。
值得注意的是，该量子算法还采用了哈密顿模拟，而大多数其他连续优化方法都没有使用这种基本原理。与经典梯度下降法不同，它可以利用量子隧穿来避免陷入局部极小值；因此，它有可能找到非凸函数的全局极小值。在具体的端到端问题中，基于哈密顿模拟的量子方法能在非凸优化中产生优势，这是未来工作的一个有趣方向。
密码学可确保计算和通信的安全。例如，用户的数据以及他们发送或接收的信息可以保密，以防恶意干扰者试图获取敏感信息。
一套统称为密码系统的算法赋予了这种安全性。破解安全性的尝试被称为密码分析，它有自己的一套算法。从历史上看，密码学和密码分析都认为经典的多项式时间算法是唯一现实的算法。量子计算的出现迫使我们考虑通过量子算法进行攻击。一般来说，我们想知道什么是密码分析的最佳算法，以便了解在最坏情况下对密码系统的影响。量子攻击的影响可能会使一组广泛使用的密码系统的安全性失效（关于破解密码系统的章节）。
更广义地说，量子密码分析可以降低密码系统的安全性（削弱密码系统部分），从而使以安全方式实现密码系统变得更加昂贵。
1）破解密码系统
如果假定某个特定数学问题很难解决，对手无法了解到关于加密内容的微不足道的信息，那么这个密码系统就被认为是安全的。最早的此类密码系统使用的是数论中的特定问题，其变体至今仍被广泛使用。这些密码系统属于公钥密码学范畴，任何用户都可以执行加密等任务，而对称密码学则不同，用户必须事先共享密钥。
量子计算机使用量子算法来解决计算问题，在某些情况下，它们比已知的最佳经典技术更快。当量子计算机应用于密码系统中的底层计算任务时，与经典方法相比，量子算法的大幅提速可能会破坏密码系统，因为对手可以在不可忽略的程度上有效地学习加密信息。量子计算最先发现也是最著名的应用之一是肖尔算法，它破解了基于数论的公钥加密常用方法，包括因式分解、离散对数和椭圆曲线。这些公钥密码系统的应用包括隐藏信息内容的加密、防止篡改和冒充的签名，以及为对称密码学生成密钥的密钥交换。
在本节中，我们将重点讨论两种应用最广泛的密码系统：Rivest-Shamir-Adleman(RSA)和椭圆曲线。
RSA推荐的最小密钥大小为2048位。电路的优化和硬件限制的加入，使得资源估算值不断下降，但也更加切合实际。对于2048比特的密钥大小，假设最近邻连接，需要约14000个逻辑量子比特和3 × 10^9个Toffoli门。
对于椭圆曲线加密，为确保128位的安全性，推荐的最小密钥大小为256位（使用RSA达到相同的安全级别需要3072位的密钥大小）。据估计，要破解256位椭圆曲线加密算法，所需的逻辑量子比特和Toffoli门分别要比3072位RSA少三倍和100倍。
虽然基于数论问题的流行密码系统对公钥密码学来说并不安全，但存在着被认为对量子计算机安全的替代方法：例如，基于纠错码或网格的算法。这些替代计算问题被认为对经典计算机和量子计算机都很难解决。美国国家标准与技术研究院(NIST)计划在2024年之前提供相关标准，以促进实施。对称加密涉及的计算没有太多结构，量子计算机也无法破解。相反，安全性的比特数会减少。
肖尔算法之前的实验演示都是利用答案知识来优化电路，从而得出在非误差校正设备上实验可行的大小。有意义的演示应避免这种捷径，因为在现实的加密场景中不存在这种捷径。
实现肖尔算法所需的电路深度大、运算复杂、量子比特数量多，使得忠实地实现NISQ具有挑战性。不过，也有一些人试图以失去肖尔算法的保证为代价来简化实现，希望输出仍能以某种非零概率正确，这种概率可能是消失的。
一种方法是简化若干操作，使其近似。近似算法的实现，包括实验，使得对更大问题实例的成功因式分解成为可能。这种近似版本并不是通常意义上的涉及噪声电路的NISQ，而是引入了一些不可控的近似误差，以换取降低深度，获得有用结果的可能性。另一种方法是在变分优化电路中编码因式分解问题。同样，这种方法的性能也得不到保证；此外，与经典方法相比，应用于一般问题的变分优化预计最多只能有四次改进，破解密码学的希望渺茫。
对小问题的经典模拟表明，该算法可以成功，在超导量子处理器上的实验实现也是如此。一般来说，这些NISQ方法没有证据或论据表明可以扩展到与密码学相关的系统规模。
肖尔算法的存在意味着常见的RSA和椭圆曲线方案在理论上是不安全的，而资源估算已经明确了何种规模的量子硬件会破解它们。虽然目前还不存在这样的硬件，但可以利用这种设备的进展来确定过渡到抗量子加密的速度。
目前，从硬件角度来看，量子计算领域还远远没有实现能够破解实际使用的加密方案的算法。上述估计表明，所需的再资源将是数百万个物理量子比特、执行数十亿个Toffoli门、以天为单位运行。相比之下，目前最先进的量子计算技术仅需一百个噪声物理量子比特，并在演示单个逻辑量子比特方面取得了进展。
因此，最先进的硬件与破解密码系统的要求之间存在巨大差距。此外，密钥大小的线性增长将增加Toffoli门的数量，例如增加三的幂次，这可能非常可观。因此，考虑到实验挑战，首先面临风险的可能只是最敏感的数据，而不是普通交易。这些高度机密的通信可能会首先采用后量子加密技术，以避免被破解。然而，不安全的协议往往在实践中挥之不去，因此量子计算机可以利用已部署系统中尚未解决的任何漏洞。例如，在商用设备中发现了大小为768比特的RSA密钥（注意，这种大小的密钥已经可以被经典破解）。此外，用RSA或椭圆曲线加密的截获信息现在就可以存储，一旦大规模量子计算机可用，以后再进行解密。
目前正在积极研究后量子密码学候选方案的弹性。特别是，专门的量子攻击可以减少安全比特数、削弱密码系统。 经典攻击甚至破坏了某些密码系统。需要注意的是，这些攻击会影响特定方案的可行性，但也存在其他没有已知弱点的后量子候选方案。
值得进一步讨论的一个敏感领域是加密货币，因为大部分加密都依赖于被破坏的数论公钥密码学。此外，改变货币的加密协议需要大多数用户达成共识，即使克服了采用后量子加密的技术障碍，协调起来也很困难。加密货币钱包如果泄露了自己的公钥（例如，通过重复使用之前分配给该钱包的公钥进行交易），就可以使用肖尔算法破解。在单笔交易中泄露密钥的短时间窗口内也有可能受到攻击。
不同的加密货币对这类攻击的敏感程度不同；尽管如此，加密货币的挖掘并没有被破坏，只是被量子计算机削弱了。
2）削弱密码系统
肖尔算法的发现激发了人们对后量子密码学的兴趣，即研究假设存在大规模工作量子计算机的密码系统。虽然一些现有系统的安全性仍然令人信服，但其他被量子算法破解的系统则被那些能完成相同任务、但被认为能对量子攻击保持较高安全性的系统所取代。
即使密码系统没有被完全破解，其安全程度也会被量子算法削弱。密码系统的强度通常以安全比特数来量化，即n比特相当于以1/2n的概率猜出所需信息并获取受保护的内容。破解一个密码系统意味着只需要有效的尝试次数（即 poly(n)），而削弱一个密码系统的攻击仍然需要2m > poly(n) 的尝试次数，对于某个m < n。
与公钥密码系统相比，对称密钥密码技术发现得更早，功能也更少。不过，对称密钥加密法对基本数学问题的假定硬度依赖较少，因此只被量子密码分析削弱过，下文将详细讨论。
在对称密钥加密法中，通信双方共享相同的密钥K，该密钥用于加密EncK和解密DecK。通常，包括对手在内的所有人都知道加密算法(EncK、DecK)。那么，对手的任务就是在获得r对明文（信息m）和相应密文c（其加密）的情况下学习密钥。例如，可以通过强制传输某个测试信息来获取这对信息。准确地说，输入K的函数输出为：
即找到一个密钥，使所有信息都能正确加密。一种直接的攻击方法是使用蛮力测试每一个密钥；实际上，复杂的经典攻击方法在渐进缩放方面的表现并不比这种方法好。
由于量子攻击只能将复杂度中的指数减半，简单的解决方法是将密钥长度增加一倍：例如采用AES-256而不是 AES-128。这种修改会增加实施成本（即加密和通信资源的复杂性），但通常是可以承受的。此外，还有一些密码系统具有信息论上的安全保障，假设对手具有无限的计算能力，可以抵御量子攻击。
此外，值得注意的是，要充分发挥振幅放大的四次方优势，相比之下，经典的暴力破解攻击可以利用高性能经典计算机的并行性，从而增加量子方法比经典方法更有优势的n值。
对AES的经典算法攻击只降低了几个比特的安全性。更实用的是利用物理副产品（如能量消耗）的侧信道攻击。例如，在比较一个密钥和另一个字符串之间的比特时，一个翻转的值会导致逻辑增加能耗，而在相同的值下则不会发生任何情况。这两种情况会被区分开来，密钥的相关信息也会被了解。
128比特的安全性是目前推荐的最小值。
密钥可以编码为哈密顿的基态，然后应用变分法求解。预计缩放与振幅放大相同。不过，由于变分算法没有设定时间复杂性，因此求解速度可能更慢或更快。如果波动足够大，就有可能对提供最坏情况保证的密码学构成挑战。不过，没有理由期待成功概率会随着密钥大小的增加而增加，并在实践中损害安全性。另一种方法是使用振幅放大，但要根据近期设备进行调整，这样NISQ优化版本在实际实验中的表现会更好。
在这里，我们主要以对称密钥加密为例。尽管如此，假设甲骨文的构建效率很高，那么将有效比特数的安全性减半的放大效应对于计算问题来说是通用的。从密码学的角度来看，这种攻击是温和的，可以通过将方案中的安全比特数增加一倍来抵消。在实践中，密钥大小的增加可能会在某些应用（如加密货币）中造成不便，但基本安全性不会受到威胁。
工程和科学领域的许多应用都依赖于微分方程的求解。因此，这在各行各业的研发高性能计算(HPC)工作负载中占了很大一部分。
不难理解，人们提出了许多在量子计算机上加快微分方程求解速度的建议。目前的共识是，我们缺乏令人信服的证据来证明量子技术在解决行业相关问题上的实际加速效果。
不过，该领域进展迅速，仍有可能带来一些惊喜。已经考虑的一些主要应用领域包括：
- 计算流体动力学(CFD)。通常涉及Navier– Stokes方程的模拟。依赖CFD模拟的主要行业有：汽车、航空航天、土木工程、风能和国防。虽然大多数模拟的重点是固体物体上的气流或流体流动，但其他过程（如发泡）的模拟也很重要。大型CFD计算通常达到petaflop级，并在数百万个CPU内核上运行。
- 地球物理建模，涉及波方程的模拟。主要行业有：石油和天然气、水电、地球物理。大型地震成像模拟可以轻松达到petaflop级。
- 有限元法(FEM)用于研究固体物体的结构特性。主要行业包括：土木工程、制造（包括汽车）、航空航天、国防。模拟规模通常比CFD稍小，但仍需要大型HPC集群。
- 麦克斯韦方程和热方程可应用于芯片设计和其他电子元件设计，以及导航和雷达技术。
- 涉及随机微分方程(SDE)模拟的风险建模广泛应用于金融（尤其是衍生品定价）、保险和能源市场。最大的风险建模模拟可以轻松达到petaflop级，但通常比CFD计算更加分散。
- 涉及弗拉索夫方程模拟的等离子体物理学在核聚变研究中非常普遍。
微分方程可根据一些特性进行分类：(a)普通微分方程与偏微分方程，取决于微分变量的数量；(b)随机微分方程与确定微分方程，取决于函数是否是随机变量；(c)线性微分方程与非线性微分方程。我们将主要关注线性偏微分方程，因为它是实际问题中最大的一类，只顺便评论一下随机或非线性微分方程；为了对微分方程进行数值求解，我们需要指定一种离散化方案。
主要有以下两类(i)有限差分法及其多种变体，包括有限元法(FEM)和有限体积法(FVM)，并结合各种支持网格和预处理选择。在有限差分框架中，连续空间在网格上离散化，连续算子由相邻网格点上的有限差分运算代替。或者 (ii)，可以通过在函数基础（傅里叶、赫米特等）上展开来离散空间，并在此空间内求解离散问题。
第二类方法通常被称为频谱法。线性微分方程可以映射为线性方程组。如果人们对非常高的精度感兴趣，需要非常精细的离散化，那么线性方程组可能过于庞大，无法在经典计算机上直接进行数值求解。特别是，如果需要高精度的时间积分结果，和/或包含许多连续变量的系统，那么模拟在时间和内存上都会面临挑战。
尽管量子线性系统求解器的类似估算结果也会产生类似的资源估算结果，但迄今为止还没有很多这样的资源估算结果。不过，经典PDE求解器的大部分技术是寻找适当的预处理方案来控制条件数。有文献表明，一类常见的预处理方案在量子算法框架内有效，但目前还不清楚这种情况是否更普遍。
已有文献对上述端到端问题给出了一个明确的资源估计，估计要打败最好的经典求解器，“所需的计算精度为0.01%：如果不考虑甲骨文成本，期望计算精度为0.01需要近似电路宽度340和电路深度10^25，如果包括甲骨文成本，则电路宽度和深度分别为10^8和10^29。”这些估算结果并不十分令人鼓舞，但使用最新的合成和仿真方法，可以将它们减去许多数量级。
预计使用最先进的量子线性系统求解器，Tofolli门的数量可以降低几个数量级，根据具体设置，可能在10^(11-15)之间。
关于PDE求解器的NISQ实现，已经提出了各种建议；其思路是从PDE L|ψ(θ)⟩ = |b⟩的某种离散化开始，其中|ψ(θ)⟩是适当选择的变分电路，然后优化电路参数。这就是变分量子算法的一个例子。很难想象在NISQ体系中能达到足够的规模和精度，从而与最好的经典求解器竞争。
虽然PDE的模拟是最重要的大规模计算任务之一，在工业领域的HPC工作负载中占有相当大的比例，但目前量子求解器的优势在四维以内仍然过于有限。要想找到量子算法在PDE（超越自证化学）方面的杀手级应用，就必须找到高维PDE的重要应用，这些PDE需要非常高精度的求解，同时涉及相对简单的几何或初始条件，而且目前无法用任何经典方法精确求解。
内存使用率仍有可能大幅提高，但目前这还不是经典PDE求解的瓶颈。最近的进展表明，在非常特殊的情况下，量子硬件可能仍有大幅提升的空间，但目前还不清楚这些情况的实用性或相关性如何。
虽然多个行业都能从量子计算中获益，但金融服务业历来是量子技术的先行者，在量子金融领域投入了大量研发力量。金融业有一个显著特点，那就是更强大、更精确的模拟可以带来直接的竞争优势，而其他行业则很难做到这一点。在这一应用领域，研究人员努力为金融服务感兴趣的用例寻找量子加速。
已经提出了许多量子解决方案的候选用例，例如：
- 衍生品定价（如期权和债务抵押债券(CDO)。衍生品是建立在标的资产基础上的金融工具，可能以潜在的复杂方式依赖于资产的价值。在衍生品定价问题中，我们需要确定金融工具的公允价格，而这通常取决于基础资产在以后某个日期的预期价值。一个类似的相关问题被称为计算希腊值 [3]。 金融衍生工具的希腊值是确定衍生工具对问题中各种参数的敏感度的量。
例如，期权的希腊值由期权价值相对于某些参数的导数给出，如 ∆ := ∂V/∂X ，其中V是期权的价值，X是标的资产的价格。
- 信用估值调整(CVA)。信用估值调整是指确定衍生工具、投资组合或其他金融工具的公允价格的问题，这些工具是以信用方式提供给购买者的，并且考虑到了购买者（可能很差）的信用评级和违约风险。CVA通常由无风险投资组合与考虑到违约可能性的投资组合价值之间的差额给出。
- 风险价值(VaR)。风险分析有多种形式，VaR就是一个常见的例子。风险价值衡量的是在固定置信区间内，金融工具（如投资组合）在预定时间间隔内可能损失的总价值。
例如，投资组合的风险价值表明，在95%的概率下，投资组合的损失不会超过Y美元。类似的技术也适用于相关的信用风险值(CVaR)问题。
- 投资组合优化。投资组合优化的目标是确定资金在可投资资产范围内的最优分配，从而使投资组合的收益最大化、风险最小化，同时遵守其他约束条件。
虽然还有更多的用例和几种产生量子加速的方法，但从广义上讲，许多用例都源于量子改进的两种途径之一：蒙特卡罗方法（用于模拟随机过程）的量子增强和约束优化。
在第一种情况下，方法通常涉及将一个相关的、针对特定问题的函数编码到量子态中，然后使用量子振幅估计从分布中采样，采样次数比经典蒙特卡罗方法少四倍。在第二种情况中，一个金融用例被简化为一个约束优化问题，并使用量子优化算法来解决问题。
在这两个领域研究的用例中，期权定价和投资组合优化往往分别是蒙特卡罗和约束优化问题的典型例子，与之相关的量子算法的后续工作也最多。此外，这两类问题在金融服务业使用的经典计算中占有相当大的比重；尽管其中的方法、注意事项和复杂性（通常）可以很容易地应用到其他相关用例中。
1）投资组合优化
投资组合优化(PO)问题是指给定一组可能的投资资产，找出这些资产的最佳资金分配方案，从而实现收益最大化和风险最小化。通常所说的马科维茨模型因其简单和广泛的适用性而被广泛应用于金融业。
复杂的约束条件、交易成本函数和对问题的修改可用于模拟现实的现代投资组合优化问题。对这些优化问题进行数值求解是金融服务业务现有工作流程的常规部分。目前，已经提出了几种解决投资组合优化问题的量子方法，每种方法都有各自的优点和缺点。
已经解决的端到端实际问题包括：
考虑一组具有固定总预算的n种可投资资产。定义wi ∈ R为总预算中投资于资产i的部分。让r成为一个已知的n维向量，表示每种可用资产的预期收益，即每种资产的价值在某个确定的时间段内预期增长的百分比。
让Σ∈Rn ×n作为协方差矩阵，用于控制资产收益率偏离均值r的随机（可能相关）波动。协方差矩阵可用来定义投资组合的“风险”wTΣw，也就是在假设基础模型准确的情况下，投资组合产生的收益的方差。用1表示全一向量，对于任意一对向量u、v，让⟨u、v⟩表示u和v之间的标准内积：
通常情况下，对于某个预先指定的ϵ值，找到一个能使目标函数达到加法误差ϵ的优化向量是令人满意的。
与优化问题的通常情况一样，问题的表述对求解策略和问题难易程度有很大影响。如果PO问题是无约束和连续的（即每个wi都是实数），那么问题就相对容易。如果施加了凸不等式约束，如只长约束或周转约束，问题就比较难，但仍然可以用相对有效的凸优化方法来解决。
与此相反，如果将问题离散化（使w现在代表正在交易的资产份额或手数的整数），或应用上述某些约束条件（如整数值约束条件，如万有引力），那么问题就会变得非凸，解决起来也会难得多。一般来说，在离散约束条件下，该问题可以表述为混合整数程序(MIP)的一个实例，MIP是NP-complete，因此在普遍认为的假设条件下很难在多项式时间(n)内求解。或者，通过对整数变量进行二元编码，可以将其表述为二次无约束二元优化(QUBO)实例。
这些表述允许使用组合优化的量子算法；例如，MIP表述可以用分支和边界方法求解，QUBO表述可以通过Grover类型的方法求解，或通过（NISQ友好的）量子退火方法启发式地求解。
上文讨论的PO量子算法继承了其基本原理（即QLSS、层析成像和经典数据加载）的许多注意事项。一个突出的注意事项是，基于QLSS的方法依赖于一些特定实例参数，如果不进行数值模拟，很难预测这些参数。渐进加速取决于对这些参数缩放的假设。此外，要实现提速，必须在大型数据集上使用对数深度QRAM，这虽然在理论上是可行的，但却带来了实际挑战。
分支与边界方法不需要对数深度QRAM就能实现近乎二次方的加速，因为运行时间将由指数树大小因子支配（尽管快速QRAM有助于将每一步求解凸松弛所需的时间减少 poly(n) 倍）。不过，这种方法需要注意的一点是，要获得二次加速，MIP的凸弛豫（即SOCP）需要连贯求解。原则上，这总是可行的，但可能需要大量的连贯经典运算以及额外的poly(n)时间和空间开销。
目前，已经提出了几种利用量子解决方案进行投资组合优化的替代方法。
- NISQ-HHL。这项工作通过采用中电路测量和条件逻辑，对上述算法进行了推广，从而获得了QLSS的NISQ版本，该版本可轻松解决PO问题。
- QAOA 方法。这些方法通常使用二次目标函数，但将wi∈{0, 1} 视为二进制变量，表示某项资产是否属于投资组合的一部分（大大偏离了正常表述）。通过在目标函数中加入惩罚来处理约束条件。另外，也可以通过选择巧妙的解析式，或通过测量投影到可行空间来强制约束。
- 量子退火方法。与前一种方法一样，这些方法要求将问题表述为二元优化问题。不过，在这种情况下，它们通常采用MIP方案，并通过几种可能的编码方式之一对整数进行二进制编码（因此，二进制变量的数量将大于n）。还可以使用各种技巧将PO问题中的约束条件纳入目标函数，从而得到所需的QUBO，然后使用量子退火器对其进行求解。
针对PO连续公式的QIPM方法（以及更普遍的基于QLSS的技术）有可能为PO问题提供多项式（但亚二次方）的加速。然而，这些提速受制于对某些特定实例参数缩放的猜想，而且初步的经验估算并没有显示出最大提速。
无论如何，上述资源估算表明，在这种情况下实现QIPM所需的非Clifford资源是令人望而却步的，即使问题的大小用经典计算机来解决也是微不足道的。对于足够大的资产集，这个问题可能存在渐近量子优势，但如果不对量子算法和底层基元（如QRAM、QLSS）进行重大改进，这种方法不太可能取得成果。即使进行了这样的改进，该算法也只能提供充其量是亚二次方的多项式加速，从而大大限制了这种方法的上升潜力。
离散公式的分支与边界方法有可能实现更大的二次加速，但正如在组合优化中类似Grover的二次加速中观察到的那样，目前还不清楚二次加速是否足以克服固有的较慢量子时钟速度和实际实例大小的容错量子计算所带来的开销。
2）蒙特卡罗方法：期权定价
许多金融工具都需要估算随机变量的某个函数在某个时间窗口内的平均值。要计算这个平均值，可以使用蒙特卡罗方法对时间窗口内的随机过程进行多次模拟，评估函数（可能取决于随机变量在整个窗口内的运行轨迹），并对平均值进行数值估算。
虽然问题的设置和细节可能因使用情况而异，但基本方法往往非常相似。作为这个问题的典型例子，我们将重点讨论衍生品（如期权）的定价问题，但我们要指出的是，这些结果中的很多都可以用于其他用例，如计算希腊字母、信用估值调整、风险价值等。
衍生品是一种金融工具，粗略地说，它允许相关各方在资产（如股票）增值或贬值时获益，而无需持有资产本身。其中一种衍生工具被称为“期权”，它是一种允许持有人在未来某个预定时间（行权窗口）或之前，以固定的、预定的价格（执行价格）购买（看涨期权）或出售（看跌期权）相关资产的合约。如果期权持有人选择行使期权，期权卖方有义务卖出或买入资产。
那么，应该如何确定期权的价格（即持有人必须为合约支付的金额，而不是行权价）呢？众所周知的Black-Scholes（或Black-Scholes-Merton）模型提供了一种期权定价方法，它对标的资产和合约规则做了一些假设。还可以考虑更复杂的期权，如合约中包含多种资产（如一篮子期权）、多种可能的行权窗口（如百慕大期权或美式期权）等。
通常情况下，期权的定价方法是，对标的资产的价值进行蒙特卡罗取样，确定给定头寸的预期利润或损失，并将其转化为购买者必须支付的价格。对卖方而言，潜在下跌空间较大的期权购买成本应更高。
假设你想为基于标的资产的期权定价。该资产的价格是一个随机变量X、它遵循一个已知（或假定）的随机过程，该随机过程模拟了标的资产的市场行情。期权有一个已知的报酬函数f(X)（例如，每个时间步长的资产价格减去轨迹上的行权价格的差额，或者零，取两者中较大者）。对于依赖于一种以上标的资产或多个不同时间点的资产价格的期权，随机变量X将代表一 个数据向量，其中包含计算收益所需的所有信息。
考虑到这些输入，端到端的问题是计算出预期收益 EX(f(X))的估计值，这个估计值要大概率在一定的误差容限ϵ之内。然后利用这个数量来确定期权的价格。
利用假定的资产价格随机模型，我们可以建立一个期权平均收益的随机微分方程。在有限的情况下，我们可以通过分析计算平均报酬，例如著名的布莱克-斯科尔斯欧式看涨期权价格公式——1997年诺贝尔经济学奖就是通过该公式获得的。
资产在t时的价格的布莱克-斯科尔斯微分方程为：
人们提出了数值求解随机微分方程的量子方法，包括有限差分法、哈密顿模拟法和量子随机游走法等。在现实世界的许多衍生品定价应用案例中，底层微分方程变得难以解决。因此，计算期权平均收益最常用的经典方法不是求解随机微分方程，而是直接对随机过程X进行蒙特卡罗采样。为此，我们需要在选定的时间范围内生成大量的价格轨迹，然后用数值计算平均报酬。
如果需要不同的金融工具，如风险价值或信用估值调整，需要计算的函数可能会有很大不同，但方法往往是相同的：多次模拟基本的随机演化，并对所需数量进行数值估计。
有许多类型的期权和衍生品可能无法被这些简单的模型准确地捕捉到。有些报酬函数是路径依赖的，因此不能简单地使用某个固定时间的资产价值来计算成本，而 是成本取决于随机变量在每个蒙特卡罗样本中的轨迹。
此外，蒙特卡罗采样的经典方法通常允许大规模并行，因为对底层资产的每次模拟都可以独立完成。相比之下，解决这一问题的量子算法需要采用串行方法，因为量子算法中的子程序必须一个接一个地运行，而无需测量和重启，这样才能实现四次方优势。如果还考虑到量子设备的时钟速度较慢，那么量子速度超过经典方法的要求就更加严格，因为要实现实际优势，需要更大的问题规模。
在文献中，作者对量子计算机上期权定价所需的资源设定了上限，并提出了量子硬件开发的目标，即能够超越经典蒙特卡罗方法。特别是，作者估计量子设备每秒需要能够执行约10^7层T门。此外，容错执行的代码距离需要选得足够大，以支持总计10^10次无差错逻辑运算。这些要求转化为约50MHz的逻辑时钟速率，才能与当前的经典蒙特卡罗方法相媲美。
考虑到物理硬件的现状和目前已知的在表面代码中执行逻辑门的方法，这一时钟速度比可预见的可能速度要快几个数量级。
虽然导数定价对资源的要求相当严格，但这仍然是一个积极研究的领域。
最近，人们对探索量子计算与机器学习之间的相互作用产生了浓厚的兴趣。量子资源和量子算法在传统机器学习管道的所有主要部分都得到了研究：(1) 数据集；(2) 数据处理和分析；(3) 导致假设族的机器学习模型；(4) 学习算法。
在本节中，我们主要考虑应用于经典数据的量子算法。这些方法包括以量子线性系统求解器（或更广义的量子线性代数）为基础的算法，这些算法是量子加速经典学习算法的可能来源。这些算法还包括量子神经网络（使用变分量子算法框架）和量子内核，其中经典机器学习模型被量子模型取代。此外，我们还将讨论旨在加快数据分析任务的量子算法，即张量主成分分析(TPCA)和拓扑数据分析。
量子机器学习是一个活跃的研究领域。然而，随着新成果的发现，评估结果表明，在所考虑的量子机器学习算法中，很少有能在不久的将来显示出量子优势的。这一结论源于许多因素，包括将经典数据加载到量子设备和通过断层扫描提取经典数据的问题，以及经典“去量化”算法的成功。更专业的任务，如张量 PCA 和拓扑数据分析，可能会在某些情况下提供更大的多项式加速（即优于二次方），但其应用范围并不广泛。最后，量子神经网络和量子核方法等其他技术包含启发式元素，这使得进行具体分析的端到端资源估算具有挑战性。
1）通过量子线性代数进行量子机器学习
具有张量乘结构的高维空间线性代数是量子计算的主力，也是机器学习(ML)的主力。因此，人们努力为各种学习任务寻找量子算法也就不足为奇了，这些任务包括但不限于：聚类分析、主成分分析、最小二乘拟合、推荐系统、二元分类和高斯过程回归。
所有这些任务的主要计算瓶颈之一是处理大型矩阵。量子线性代数可以显著加快这类问题的处理速度，量子线性系统求解器(QLSS)就是一个很好的例子。可行性的主要问题是：
- 量子线性代数能否完全去量化用于ML任务？- 经典训练数据能否高效地加载到量子随机存取存储器(QRAM)中？- 避免上述陷阱的量子ML算法能否解决相关的机器学习问题？
根据我们目前的理解，要想获得显著的量子优势，就必须同时具备上述条件，而这在迄今为止分析的具体应用中尚未发现，不过适度提速还是有可能的。
由于许多量子机器学习提案都是一次性的，而且通常都是启发式的，因此我们将探讨三个具体应用，而不是涵盖每项建议。每个例子都解释了要解决的端到端问题，并大致说明了所提出的量子算法是如何解决该问题的，从而得出其主要复杂度。在每种情况下，量子算法都假定可以访问快速相干数据访问（对数深度QRAM），并利用量子基元求解线性系统（以及更广泛的线性代数）。
在某些条件下，这些基本原理可能比在指数级大的向量空间中处理所有向量项的经典方法快上数倍。然而，对于这些例子来说，仔细定义端到端问题至关重要，因为指数级优势可能会在读出步骤中丧失，在这一步骤中，必须从编码线性代数问题解的量子态中检索机器学习问题的答案。在下面的三个例子中，这都是通过某种形式的振幅或重叠估计来实现的。
此外，我们还注意到，即使这些量子算法的速度比操纵完整状态向量的经典算法快出指数级，但在某些情况下，这种提速已经通过仅对向量条目进行采样的算法“去量化”了。具体来说，对于某些端到端问题，存在经典的量子启发算法，其解决问题的时间仅比量子算法慢多项式。
假设量子算法可以快速QRAM访问经典数据，与假设经典算法可以快速采样查询(SQ)访问数据类似。我们注意到，大多数基于线性代数的机器学习任务，其量子算法也在某种程度上被去量化了。不过，在某些情况下，如果量子算法能够利用相关矩阵中的额外结构（如稀疏性），而经典算法无法利用这些结构，那么量子算法仍有可能具有指数级的优势。
这些建议和其他建议的最大问题是如何获取量子叠加中的经典数据。这些量子机器学习算法假定我们可以在多对数(N)时间内加载N个条目向量或N^2个条目矩阵。虽然已经有人提出了高效的量子数据结构（即QRAM）来完成这项任务，但它们也引入了一些注意事项。
为了在对数(N)时间内连贯地加载N个数据，QRAM使用了许多以树形结构排列的ancilla量子比特。要加载N个大小的数据，QRAM数据结构需要O(N)个量子比特，这比上述算法中使用的O(log(N))个数据量子比特要大得多。这个空间复杂度还不包括量子纠错和容错计算的开销，特别是并行提炼魔态所需的大量空间资源。因此，我们还不知道是否有可能构建一种QRAM，既能足够快速地加载数据，又能保持适度的空间资源。
此外，通过有效地将数据表示为量子态来实现提速可能表明，在某些情况下，基于张量网络的方法也能实现类似的性能。将这一思路发挥到极致，通过对量子算法进行“去量化”，人们开发出了许多高效的经典算法。也就是说，通过对训练数据假设一个类似的访问模型（SQ访问模型），以及对输入的稀疏性和/或秩的一些假设，就可以得到近似的经典采样算法，与量子算法相比，其开销为多项式。
这就意味着，任何明显的指数级提速都必须是数据加载/数据访问假设的产物。
QLSS子程序还继承了另一个注意事项，即当涉及的矩阵条件不佳时，复杂度会很大。在上文的高斯过程回归和支持向量机示例中，这一问题得到了一定程度的缓解，因为在这些示例中，需要反演的矩阵是通过添加同一矩阵来正则化的。
据我们所知，还没有针对任何特定量子机器学习任务进行过完整的端到端资源估算。
基于线性代数的经典机器学习能否实现量子提速，很大程度上取决于量子算法的去量化程度。目前，似乎禁止对许多提出的问题进行指数级提速，但仍有可能实现较大的多项式提速。针对去量化方法的最新渐进缩放分析仍然允许在的Frobenius准则上有4次方的提速，在多项式近似程度上有9次方的提速。不过，经典算法正在稳步改进，其缩放比例可能会进一步缩小。
还值得注意的是，基于SQ访问模型的经典概率算法目前还没有在实践中使用。这可能有多种原因，包括多项式缩放性较差、访问模型可能不太适合许多实际场景，或者仅仅因为该方法是新方法，尚未经过实践检验。
另一方面，已知一些基于量子线性代数的机器学习任务无法去量化，例如在内核矩阵稀疏的假设下的高斯过程回归。基于SQ存取的量子启发经典算法仍将随Frobenius准则的多项式而扩展，尽管其他经典算法可能能够更直接地利用稀疏性。满足这些标准的原型矩阵是稀疏的单元矩阵（例如由局部量子门自然实现的矩阵），这也许并不令人意外。 为了避免指数级开销，端到端问题必须不需要指数级的小精度。
2）通过基于能量的模型进行量子机器学习
机器学习中的一类重要模型是基于能量的模型，它在很大程度上受到了统计力学的启发。基于能量的模型的目标是训练一个物理模型（即调整一组粒子之间的相互作用强度），使模型在热平衡时与训练集密切匹配。基于能量的模型是生成模型的一个例子，因为它们一旦经过训练，就可以通过从模型的热分布中采样，形成与训练集相似的新示例。
基于能量的模型与物理学有很深的联系，因此是各种量化形式的主要候选模型。然而，量子方法面临的一个挑战是，学习问题的统计力学性质往往也适合高效、近似的经典方法。因此，最好的量子算法也可能是启发式的，这阻碍了端到端的复杂性分析。虽然目前基于能量的模型不如深度神经网络应用广泛，但它们是机器学习领域的一个重要概念发展，并且由于其良好的理论基础及其与统计力学的联系而继续受到关注。
目前有许多将基于能量的模型推广到量子机器学习的建议。量子算法可能有助于训练经典图形模型。我们还可以通过允许每个顶点上的物理系统是量子的，以及允许系统间的相互作用是非交换的，来推广模型本身。
量子方法训练经典模型有两大注意事项，既适用于退火，也适用于容错设置。(i) 经典启发式算法，如贪婪法或对比发散法，通常在实践中表现良好，是现有经典分析的首选方法。这些方法通常也是高度可并行的。如果量子算法比速度较慢的精确经典方法更快，但如果速度更快的近似经典方法已经足够，那么这可能并不重要。(ii)人们希望启发式量子退火方法表现更好的情况可能不是相关问题，例如基于高度规则晶格的问题。
量子退火法的一个注意事项是，损失函数的梯度与样本平均值并不完全相关，因此必须采取不完善的变通方法。与机器学习中的许多其他情况一样，由此产生的端到端解决方案是启发式的，其有效性需要经验证明。
虽然基于能量的模型可以很自然地扩展到量子领域，但在具体的端到端经典机器学习问题上，仍然缺乏量子优势的决定性证据。由于启发式量子方法的核心地位，这些方法的前景仍存在一些不确定性。人们可能希望这些启发式方法能在某些特定环境中优于经典启发式方法，但经典启发式方法的成功和近似经典方法的有效性为在这一领域实现任何量子优势带来了巨大障碍。
3）张量PCA
推理问题在机器学习中扮演着重要角色。最常用的方法之一是主成分分析(PCA)，它是一种从潜在噪声数据流中提取最重要信息的技术。
在数据由秩-1向量加上高斯噪声生成的特殊情况下，即尖峰矩阵模型，众所周知，在大稀疏向量极限信噪比存在相变。在过渡点之上，主分量可以有效地恢复，而在过渡点之下，主分量则根本无法恢复。在该问题的张量扩展中，有两个过渡点。一个是信息理论上的，在此点以下无法恢复主成分；另一个是计算上的，在此点以下可以恢复主成分，但效率不高，而在此点以上则可以有效恢复。
因此，张量PCA问题提供了一个更为丰富的数学环境，它与最优化和自旋玻璃理论有关联；然而，张量PCA框架是否有自然的实际应用还不清楚。有人提出了张量PCA的量子算法，该算法对尖峰张量模型具有可证明的运行时间保证；与经典算法相比，该算法的速度可能提高了四倍，而且与其他经典方法相比，它能以更小的信噪比从噪声中有效地恢复信号。
尖峰张量模型似乎与任何实际问题无关。此外，高效恢复要求信噪比相当高，而这在现实世界中可能不会发生（当发生时，不清楚将问题表述为张量PCA问题是否是最有效的途径）。
四次加速非常引人注目。目前，我们还不知道是否还有其他大规模推理问题具有类似的加速特征。
4）拓扑数据分析
在拓扑数据分析中，我们旨在计算从底层拓扑流形（给定查看数据的长度尺度）或图中采样的数据点的主要拓扑特征（连通成分和k维洞）。这些特征可能具有独立的意义（例如，宇宙中物质分布的连通成分数量），也可以用作比较数据集的通用特征。
针对这一问题的量子算法利用了量子比特寄存器高效存储代表系统状态的能力，这使得量子算法在某些情况下比已知的经典算法更高效。
考虑到纠错带来的巨大开销，计算（持久）β数的量子算法似乎不太可能为当前感兴趣的计算带来实际优势。这是因为与经典方法相比，量子算法在这项任务中的速度提升仅为四次方，而经典算法在通常考虑的k ≤ 3机制中是高效的。
如果能找到更多数据集，其中的高维（持久）β数很大，而且在计算相对误差方面具有实际意义，那么量子算法就可能具有实际意义。
5）量子神经网络和量子核方法
使用量子计算机作为机器学习模型通常有两种方法：量子神经网络和量子核方法。
许多早期的想法都是受近期NISQ设备的限制而产生的。尽管如此，并非所有后续提案都能在NISQ设备上实现。此外，这些建议不必局限于在NISQ设备上运行，也可以在具有明确量子纠错功能的设备上运行。
在获得某些数据的情况下，我们的目标是获得一个能模拟数据某些属性的函数或分布，我们称之为模型。首先要定义一个模型族或假设集，然后使用学习算法从这个模型集中选择一个模型。例如，在有监督的学习中，我们有数据 xi∈X，这些数据有各自的标签 yi∈Y。我们的目标是找到一个模型函数 h : X 一 Y，它能高概率地正确标注以前未见过的数据。更广义地说，这种描述包含了对量子数据进行操作的可能性，即每个xi对应一个量子态。
量子神经网络和量子内核方法使用量子计算机来协助构建模型，以取代神经网络等经典模型。具体来说，这里的模型将通过准备一些量子态来编码数据，并测量一些观测值来获得模型预测结果。
我们迄今尚未讨论的一个问题是如何将经典数据编码到量子电路中，这是构建量子模型的一个重要方面。有很多可能性，比如振幅编码或将数据编码成单量子比特旋转的旋转角度。虽然某些策略很流行，但一般来说，对于手头的特定问题来说，什么是最佳选择并不明确，因此选择数据编码策略本身就是一个启发式过程。同样的问题也延伸到量子神经网络或量子内核的选择上。虽然某些选择可能在特定问题实例中表现出色，但目前还缺乏有力的证据来说明为什么这些方法在一般情况下可能比经典方法更有优势。
虽然参数化量子电路的优化主要是量子神经网络所关注的问题，但寻找好的量子“核(kernel)”也促使人们提出了可训练核的建议，即使用参数化量子电路来构建量子核。在使用启发式方法进行参数优化的情况下，它面临着与VQA相同的挑战和考虑。
在这两种情况下，有限统计都是一个重要的考虑因素。在对参数化量子电路进行优化时，必须注意避免贫瘠高原现象，类似的效应也可能出现在核设置中，甚至可能纯粹由于数据编码电路而产生。
经典机器学习模型的使用通常是高度启发式的，以经验证据或物理直觉为指导；尽管如此，它们在解决许多计算问题时仍取得了显著的成功。本节概述的量子技术也大致遵循了这一方法（尽管在某些领域也取得了实质性的理论进展），而且没有先验的理由说明它们为什么不能同样有用。尽管如此，要对量子优势做出具体预测，尤其是对经典数据做出预测，仍具有挑战性。
即使在完全经典的环境中，我们对端到端应用的分析理解也很有限，这加剧了这种挑战。事实上，除了少数几个精选的例子之外，要想获得与其他量子算法一样完整的端到端理论分析，可能最终会面临挑战。
事实上，在量子数据领域，具体可证明优势的潜力似乎已经成熟。
参考链接：[1]https://arxiv.org/abs/2310.03011[2]https://inspirehep.net/literature/2706151
相关阅读：
每周一到周五，我们都将与光子盒的新老朋友相聚在微信视频号，不见不散！
|qu|cryovac>
你可能会错过：|qu|cryovac>